package search;

public class BinarySearch {

	// arr must be sorted with distinct values
	public static int search(int[] arr, int num){
		
		int begin = 0;
		int end = arr.length - 1;
		int mid;
		
		while(begin <= end){
			
			mid = begin + (end - begin)/2;
			// int mid = (start + end) >>> 1; // another approach
			// int mid = (start + end)/2; // wrong way due to overflow problem
			
			if(arr[mid] == num){
				return mid;
			}else if(arr[mid] > num){
				end = mid - 1;
			}else{
				begin = mid + 1;
			}			
		}
		
		//return -(begin + 1); // returns "- insertion point - 1" e.g. arr = {1,3,5,7,9} and num = 2 result is -2
		return -1;
	}
	
	
	/*
	 * optimized binary search 
	 * 
	 * if the given number is not found and it's between its smaller and greater number, then the given number is 
	 * not present in arr. In this case, it returns both smaller and greater number. And search terminates.
	 * 
	 * output can be simplified using boolean variable if required
	 * 
	 * */
	public static int[] searchOptimized(int[] arr, int num){
		
		int begin = 0;
		int end = arr.length - 1;
		int mid;
		
		while(begin <= end){
			
			mid = begin + (end - begin)/2;
			
			if(arr[mid] == num){
				return new int[]{arr[mid]};
			}else if(mid+1 < arr.length && num > arr[mid] && num < arr[mid+1]){
				return new int[]{arr[mid], arr[mid+1]};
			}else if(arr[mid] > num){
				end = mid - 1;
			}else{
				begin = mid + 1;
			}			
		}
		
		return null;
	}
}
